/**
 * 150. 逆波兰表达式求值
 * https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
 */
public class Solutions_150 {
    public static void main(String[] args) {
//        String[] tokens = {"2", "1", "+", "3", "*"};  // output: 9
//        String[] tokens = {"4", "13", "5", "/", "+"};  // output: 6
        String[] tokens = {"10", "6", "9", "3", "+",
                "-11", "*", "/", "*", "17", "+", "5", "+"};  // output: 22

        int result = evalRPN(tokens);
        System.out.println(result);
    }

    /**
     * 解法：
     * 利用栈存储数值
     * 遇到运算符时，取出栈顶的两个数值，进行对应的运算操作，并将结果再压入栈中
     */
    public static int evalRPN(String[] tokens) {
        // 创建数组作为栈，长度为字符串数组长度的一半加 1
        int[] stack = new int[tokens.length / 2 + 1];
        int idx = 0;
        for (String token : tokens) {
            switch(token) {
                case "+":
                    stack[idx - 2] = stack[idx - 2] + stack[idx - 1];
                    idx --;
                    break;
                case "-":
                    stack[idx - 2] = stack[idx - 2] - stack[idx - 1];
                    idx --;
                    break;
                case "*":
                    stack[idx - 2] = stack[idx - 2] * stack[idx - 1];
                    idx --;
                    break;
                case "/":
                    stack[idx - 2] = stack[idx - 2] / stack[idx - 1];
                    idx --;
                    break;
                default:
                    // 数值
                    stack[idx++] = Integer.valueOf(token);
            }
        }
        // 最终栈中，只有一个元素，即是表达式的结果
        return stack[0];
    }
}
